The Counter (CTR) Mode
Counter (CTR) mode takes a different approach to most other modes of operation. It does not even use the block cipher's encryption function on the message itself!
The encryption process begins by dividing the message into blocks with length . Then, an initialisation vector (IV) of length is randomly generated. However, instead of passing the -th block to , CTR mode takes the IV and appends to it a counter encoded as a binary string of length and inputs this into . The -th message block is then XOR-ed with the output to produce the -th ciphertext block:
The final ciphertext is obtained by concatenating all ciphertext blocks and prepending them with the initialisation vector, which is necessary for decryption just as with CBC mode.
This process essentially turns a block cipher into a stream cipher where the IV and the counter are used to generate a keystream which is then XOR-ed with the message.
The decryption procedure is almost equivalent - the IV is extracted from the ciphertext and the rest of it is divided into ciphertext blocks . The -th ciphertext block is XOR-ed with the output of, notice, after passing it the concatenation of the IV and encoded as a binary string of length .
That's right - the decryption function of the block cipher is not even used! This means that the encryption function does not need to even be invertible, i.e. it does not need to be a pseudorandom permutation (PRP), but can simply be a pseudorandom function (PRF). This is only one major advantage of CTR mode. Another one is the fact that both encryption and decryption are parallelisable, which makes them excellent candidates for optimisation. These two factors, combined with the security provided by this mode, are the reason for CTR's extensive use.
Security of CTR Mode
So long as the initialisation vector is chosen uniformly at random and the block cipher used is secure, i.e. it uses a pseudorandom function (or permutation) for its function, CTR mode will be CPA-secure.
Proof: CPA-Security of CTR Mode
First suppose, towards contradiction, that there is an efficient adversary Eve that after querying with messages and obtaining their ciphertexts , can distinguish with probability if a ciphertext is the encryption of or , for some messages and , which are also allowed to be one of the previously queried messages.
Consider the case where the messages and are only a single block long. If instead of the PRF , the CTR encryption used a truly random function , then Eve would lack any information and so she would only be able guess at best with probability whether a ciphertext belongs to or . This, however, is a contradiction because she would be able to distinguish with non-negligible probability the output of a PRF from the output of a truly random function. Therefore, no such adversary can exist.
This reasoning assumes that the IV is never reused, but since the IV is supposed to be chosen uniformly at random, this can happen. So we need to show that this happens with only negligible probability.
Indeed, the adversary Eve makes queries which means messages with IV's. Each IV is chosen uniformly from , so the probability that an IV is repeated is which is negligible, since Eve must be efficient and therefore needs to be polynomial.
IV Reuse Attack
If you have two ciphertexts and that are the CTR-mode encryptions of two messages and which where encrypted with the same initialisation vector and the same secret key and you know one of the messages - for example - then you can easily decrypt the other message .
The first step is to XOR the two ciphertexts and to obtain the XOR of the two messages and , since the XOR of something with itself is 0 and XOR-ing with 0 has no effect.
The second and final step is to XOR this result with the known message to recover the unknown message :
This attack clearly illustrates that initialisation vectors should never be repeated.